package com.leecode;

/**
 * 搜索旋转排序数组,你的算法时间复杂度必须是 O(log n) 级别。
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * 你可以假设数组中不存在重复的元素。
 *
 * <p>
 * public int search(int[] nums, int target) {
 * int low = 0, high = nums.length-1, mid;
 * while(low <= high){
 * mid = (low+high) >>> 1;
 * if(nums[mid] < target){
 * // 中值在右区间，目标值在左区间，需左移
 * if(nums[low]>nums[mid] && nums[low]<=target) high = mid-1;
 * // 正常情况，右移
 * else low = mid+1;
 * }else if(nums[mid] > target){
 * // 中值在左区间，目标值在右区间，需右移
 * if(nums[low]<=nums[mid] && nums[low]>target) low = mid+1;
 * // 正常情况，左移
 * else high = mid-1;
 * }else return mid;
 * }
 * return -1;
 * }
 */
public class Leet33 {
	public static void main(String[] args) {
		int[] ints = new int[]{4, 5, 6, 7, 8, 1, 2, 3};
		System.out.println(new Leet33().search(ints, 8));
	}

	/**
	 * 考点:二分的"左选,右选"条件
	 * 平时接触的二分都是比mid小就左边,比mid大就右边,这种情况见多了导致产生"所有的二分都是这种情况"错觉,这题考察的就是如何清晰写出"走左边,走右边的条件"
	 */
	public int search(int[] nums, int target) {

		return 0;
	}
}
